﻿template <class type> class list
{
public:
	bool remove(int pos);
	void add(const type& data);
	type operator[](int pos);
	bool insert(int pos, const type& data);
	bool empty();
	int size();
};

template <class type> class double_link_list : public list<type>
{
private:
    struct element
    {
        type data;
        element* prev;
        element* next;
    };

    element* begin;
    element* end;

    int mSize;

public:
    double_link_list()
    {
        begin = NULL;
        end = NULL;
        mSize = 0;
    }

	bool remove(int pos)
	{
		if(begin == NULL)
		{
			return false;
		}
		if(pos > size())
		{
			return false;
		}

		element* atPos = begin;

		for(int i = 0; i < pos; ++i)
		{
			atPos = atPos->next;
		}

		if(atPos->prev != NULL)
		{
			atPos->prev->next = atPos->next;
		}
		if(atPos->next != NULL)
		{
			atPos->next->prev = atPos->prev;
		}

		delete atPos;
		--mSize;
		return true;
	}

    void add(const type& data)
    {
        element* temp = new element;
        temp->next = NULL;
        temp->prev = NULL;
        temp->data = data;

        if (mSize == 0)
        {
            begin = end = temp;
            ++mSize;
        }
        else
        {
            temp->next = begin;
            begin->prev = temp;
            begin = temp;
            ++mSize;
        }
    }

	type operator[](int pos)
	{
		element* atPos = begin;

		for(int i = 0; i < pos; ++i)
		{
			atPos = atPos->next;
		}

		return atPos->data;
	}

	bool insert(int pos, const type& data)
	{
		element* insertPos = begin;

		if(insertPos == NULL)
		{
			return false;
		}

		if(pos > size())
		{
			return false;
		}

		for(int i = 0; i < pos; ++i)
		{
			insertPos = insertPos->next;
		}

		return insert(insertPos, data);
	}

	// insert before the specific element
	bool insert(element* pos, const type& data)
	{
		element* temp = new element;
		temp->data = data;

		if(pos == NULL)
		{
			// insert at the end
			temp->next = NULL;
			temp->prev = end;
			end->next = temp;
			end = temp;
		}
		else if(begin == end && begin != NULL)
		{
			temp->next = begin;
			temp->prev = NULL;

			begin->prev = temp;

			end = begin;
			begin = temp;
		}
		else
		{
			pos->prev->next = temp;

			temp->next = pos;
			temp->prev = pos->prev;

			pos->prev = temp;
		}

		++mSize;

		return true;
	}

	bool empty()
	{
		return (mSize == 0);
	}

	int size()
	{
		return mSize;
	}
};